#include <vector>
#include <assert.h>
#include <iostream>
class QuickSort
{
private:
    /* data */
public:
    static void sort(std::vector<int>& nums)
    {
        static QuickSort solution;
        solution.quickSort(nums, 0, nums.size()-1);
    }

    void quickSort(std::vector<int>& nums, int leftBound, int rightBound)
    {
        if (leftBound >= rightBound) return;
        int mid = partion(nums, leftBound, rightBound);
        quickSort(nums, leftBound, mid-1);
        quickSort(nums, mid+1, rightBound);
    }

    int partion(std::vector<int>& nums, int leftBound, int rightBound)
    {
        int pivot = nums[rightBound];
        int left = leftBound;
        int right = rightBound - 1;
        while (left <= right)
        {
            while (left <= right && nums[left] <= pivot) left++;
            while (left <= right && nums[right] > pivot) right--;
            if (left < right) std::swap(nums[left], nums[right]);
        }
        std::swap(nums[left], nums[rightBound]);
        return left;
    }
};

// int main() 
// {
//     std::vector<int> nums = {1,3};
//     // std::vector<int> nums = {1,3,5,2,7,8,9,4,6,0};
//     QuickSort s;
//     s.quickSort(nums, 0, nums.size()-1);
//     for (int i = 0; i < nums.size(); i++) {
//         //assert(nums[i]==i);
//         std::cout << nums[i];
//     }
//     std::cout << std::endl;
// }
